package com.shuo.dsa.leetcode;

import com.shuo.dsa.model.ListNode;

/**
 * Given a singly linked list L: L 0→L 1→…→L n-1→L n,
 * reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→…
 * eg: Given{1,2,3,4}, reorder it to{1,4,2,3}.
 */
public class ReorderList1 {
    public void reorderList(ListNode head) {
        if (head == null) return;
        ListNode mid = findMidNode(head);
        ListNode list2 = reverse(mid.next);
        mid.next = null;
        merge(head, list2);

    }

    private void merge(ListNode list1, ListNode list2) {
        while (list1 != null && list2 != null) {
            // 辅助局部节点一般用来存next
            ListNode list1Next = list1.next;
            ListNode list2Next = list2.next;
            list1.next = list2;
            list2.next = list1Next;
            list1 = list1Next;
            list2 = list2Next;
        }
    }

    /**
     * 反转链表(背下来)
     *
     * @param head
     * @return
     */
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            // 辅助局部节点一般用来存next
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 寻找链表中点(背下来)
     *
     * @param head
     * @return
     */
    private ListNode findMidNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
